/* 
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。


输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3

输出: [1,2,2,5,6,7]

思路1：如果两个数组未排序，可以直接拼接后整体排序
思路2：现在是两个排序数组，考虑双指针，比较数组的大小，放入新数组
思路3：对思路2优化：不使用额外的空间，双指针倒序比较，最大的放入A的末尾
*/

/**
 * @param {number[]} A
 * @param {number} m
 * @param {number[]} B
 * @param {number} n
 * @return {void} Do not return anything, modify A in-place instead.
 */
var merge = function (A, m, B, n) {
    //  双指针指向A和B的有数据的尾部
    let pa = m - 1, pb = n - 1;
    // 声明指向A数组尾部的指针
    let tail = m + n - 1;
    // 声明一个变量拿到遍历比较后的值
    var cur;
    // 循环
    while (pa >= 0 || pb >= 0) {
        // 如果a指针遍历完了
        if (pa === -1) {
            // 获取b指针的数据，同时b指针左移
            cur = B[pb--];
        } else if (pb === -1) {
            // 如果b指针遍历完了
            // 获取a指针的数据，同时a指针左移
            cur = A[pa--];
        } else if (A[pa] > B[pb]) {
            // 如果a指针数据大于b指针，拿到a指针数据，a指针左移
            cur = A[pa--];
        } else {
            // 如果b指针数据大于a指针，拿到b指针数据，b指针左移
            cur = B[pb--];
        }
        // A数组末尾指针的位置获取cur的值同时左移
        A[tail--] = cur;
    }
};


let A = [1, 2, 3, 0, 0, 0], m = 3, B = [2, 5, 6], n = 3
merge(A, m, B, n)
console.log(A);